# define _CRT_SECURE_NO_WARNINGS

#include <memory.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <windows.h>
#include <io.h>
#include <string>
#include <vector>

typedef struct _Minmax
{
	int imin = -1;
	int imax = -1;
}Minmax;

typedef struct _Result
{
	int startpos = -1;
	double scalar;
	double similarity;
}Result;

typedef struct _Data
{
	double* data;
	int len;
	char name[16];
}Data;


int getimin(double* arr, int startpos, int endpos)
{
	double temp = arr[0];
	int res = 0;
	for (int i = startpos; i <= endpos; i++)
	{
		if (arr[i] < temp)
		{
			temp = arr[i];
			res = i;
		}
	}
	return res;
}

int getimax(double* arr, int startpos, int endpos)
{
	double temp = arr[0];
	int res = 0;
	for (int i = startpos; i <= endpos; i++)
	{
		if (arr[i] > temp)
		{
			temp = arr[i];
			res = i;
		}
	}
	return res;
}

Minmax minmax(double* arr, int len, int startpos, int endpos)
{
	int intervallen = endpos - startpos + 1;
	double k = (arr[endpos] - arr[startpos]) / intervallen;

	double* horizontal = new double[intervallen];
	for (int i = startpos; i <= endpos; i++)
	{
		horizontal[i - startpos] = arr[i] - (i - startpos)*k;
	}
	
	int imin = startpos;
	int imax = startpos;
	double temp_min = horizontal[imin-startpos];
	double temp_max = horizontal[imax-startpos];
	
	for (int i = startpos; i <= endpos; i++)
	{
		if (horizontal[i-startpos] < temp_min)
		{
			imin = i;
			temp_min = horizontal[imin-startpos];
		}
		else if (horizontal[i-startpos] > temp_max)
		{
			imax = i;
			temp_max = horizontal[imax-startpos];
		}
	}

	delete horizontal;

	Minmax res;

	if (imin != startpos && imin != endpos)
	{
		res.imin = imin;
	}

	if (imax != startpos && imax != endpos)
	{
		res.imax = imax;
	}

	return res;
}

void _zigzag(int depth, double* in, int* extreme, int len, int startpos, int endpos, int maxrecursion);

void zigzag(double* in, int len, int* extreme, int maxrecursion)
{	
	if (len < 3)
		return;

	Minmax mm = minmax(in, len, 0, len - 1);

	if (mm.imin == -1 && mm.imax == -1)
	{
		return;
	}

	else if (mm.imin != -1 && mm.imax == -1)
	{
		extreme[0] = 1;
		extreme[len - 1] = 1;
		extreme[mm.imin] = -1;
		_zigzag(1, in, extreme, len, 0, mm.imin, maxrecursion);
		_zigzag(1, in, extreme, len, mm.imin, len - 1, maxrecursion);
	}

	else if (mm.imin == -1 && mm.imax != -1)
	{
		extreme[0] = -1;
		extreme[len - 1] = -1;
		extreme[mm.imax] = 1;
		_zigzag(1, in, extreme, len, 0, mm.imax, maxrecursion);
		_zigzag(1, in, extreme, len, mm.imax, len - 1, maxrecursion);
	}

	else
	{
		if (mm.imin < mm.imax)
		{/* \/\ */
			extreme[0] = 1;
			extreme[len - 1] = -1;
			extreme[mm.imin] = -1;
			extreme[mm.imax] = 1;
			_zigzag(1, in, extreme, len, 0, mm.imin, maxrecursion);
			_zigzag(1, in, extreme, len, mm.imin, mm.imax, maxrecursion);
			_zigzag(1, in, extreme, len, mm.imax, len - 1, maxrecursion);
		}
		else
		{/* /\/ */
			extreme[0] = -1;
			extreme[len - 1] = 1;
			extreme[mm.imin] = -1;
			extreme[mm.imax] = 1;
			_zigzag(1, in, extreme, len, 0, mm.imax, maxrecursion);
			_zigzag(1, in, extreme, len, mm.imax, mm.imin, maxrecursion);
			_zigzag(1, in, extreme, len, mm.imin, len - 1, maxrecursion);
		}
	}

	/*int iprev = 0;
	int i = 0;
	while (i < len)
	{
		i++;
		if (extreme[i] == 0)
		{
			continue;
		}
		if (extreme[i] != extreme[iprev])
		{
			if (extreme[iprev] == -1 && in[iprev] > in[i])
			{
				int j = iprev + 1;
				while (true)
				{
					if ((extreme[j] == 1 && in[j] > in[iprev]) || j == len - 1)
					{
						break;
					}
					extreme[j++] = 0;
				}
			}
			else
			{
				iprev = i;
				continue;
			}
		}
		if (extreme[i] == 1)
		{
			if (extreme[i] > extreme[iprev])
			{
				extreme[iprev] = 0;
				iprev = i;
			}
			else
			{
				extreme[i] = 0;
				i = iprev;
			}
		}
		else if (extreme[i] == -1)
		{
			if (extreme[i] < extreme[iprev])
			{
				extreme[iprev] = 0;
				iprev = i;
			}
			else
			{
				extreme[i] = 0;
				i = iprev;
			}
		}
	}*/
}

void _zigzag(int depth, double* in, int* extreme, int len, int startpos, int endpos, int maxrecursion)
{
	if (endpos - startpos < 3)
		return;

	if (depth == maxrecursion)
		return;
	
	Minmax mm = minmax(in, len, startpos, endpos);

	if (mm.imin == -1 && mm.imax == -1)
	{
		return;
	}

	else if (mm.imin != -1 && mm.imax == -1)
	{
		extreme[mm.imin] = -1;
		_zigzag(depth + 1, in, extreme, len, startpos, mm.imin, maxrecursion);
		_zigzag(depth + 1, in, extreme, len, mm.imin, endpos, maxrecursion);
	}

	else if (mm.imin == -1 && mm.imax != -1)
	{
		extreme[mm.imax] = 1;
		_zigzag(depth + 1, in, extreme, len, startpos, mm.imax, maxrecursion);
		_zigzag(depth + 1, in, extreme, len, mm.imax, endpos, maxrecursion);
	}

	else
	{
		if (mm.imin < mm.imax)
		{/* \/\ */
			extreme[mm.imin] = -1;
			extreme[mm.imax] = 1;
			_zigzag(depth + 1, in, extreme, len, startpos, mm.imin, maxrecursion);
			_zigzag(depth + 1, in, extreme, len, mm.imin, mm.imax, maxrecursion);
			_zigzag(depth + 1, in, extreme, len, mm.imax, endpos, maxrecursion);
		}
		else
		{/* /\/ */
			extreme[mm.imin] = -1;
			extreme[mm.imax] = 1;
			_zigzag(depth + 1, in, extreme, len, startpos, mm.imax, maxrecursion);
			_zigzag(depth + 1, in, extreme, len, mm.imax, mm.imin, maxrecursion);
			_zigzag(depth + 1, in, extreme, len, mm.imin, endpos, maxrecursion);
		}
	}
}

double mean(double* arr, int len)
{
	double sum = 0;
	for (int i = 0; i < len; i++)
	{
		sum += arr[i];
	}
	return sum / len;
}

double stddev(double* arr, int len)
{
	double mu = mean(arr, len);
	double sum = 0;
	for (int i = 0; i < len; i++)
	{
		sum += (arr[i] - mu)*(arr[i] - mu);
	}
	double rt = sqrt(sum / len);
	return rt;
}

void normalize(double* in, int len, int* extreme, double* out)
{
	double min = in[getimin(in, 0, len - 1)];
	double max = in[getimax(in, 0, len - 1)];

	double* temp = new double[len];
	memset(temp, 0, sizeof(double)*len);

	for (int i = 0; i < len; i++)
	{
		if (extreme[i] != 0)
		{
			temp[i] = (in[i] - min) / (max - min);
		}
	}

	int prev_extreme = 0;
	for (int i = 1; i < len; i++)
	{
		if (extreme[i] != 0)
		{
			double k = (temp[i] - temp[prev_extreme]) / (i - prev_extreme);
			for (int j = prev_extreme + 1; j < i; j++)
			{
				temp[j] = temp[prev_extreme] + (j - prev_extreme)*k;
			}
			prev_extreme = i;
		}
	}

	memcpy(out, temp, sizeof(double)*len);

	delete temp;
}

void scale(double* in, int len, double scalar, double* out)
{
	int outlen = (int)(len*scalar);
	for (int i = 0; i < outlen; i++)
	{
		double index = i*(len - 1) / (outlen - 1);
		int left = floor(index);
		int right = ceil(index);
		out[i] = in[left] + (index - left)*(in[right] - in[left]);
	}
}

double similarity(double* in1, double* in2, int len)
{
	double mu = mean(in2, len);
	double sigma = stddev(in2, len);

	double* normalized = new double[len];

	for (int i = 0; i < len; i++)
	{
		normalized[i] = (in2[i] - mu) / sigma;
	}

	double temp = 0;
	for (int i = 0; i < len; i++)
	{
		temp += (normalized[i] - in1[i])*(normalized[i] - in1[i]);
	}

	delete normalized;

	return temp / len;
}

int read_data(const char* file_name, double* out)
{
	FILE* fp = fopen(file_name, "r");
	if (!fp)
		return -1;
	char buff[16] = "";
	int ibuf = 0;
	char ch = 0;
	int idata = 0;
	int len = 0;
	while (true)
	{
		ch = fgetc(fp);
		if (ch != '\n' && ch != EOF)
		{
			buff[ibuf++] = ch;
		}
		else
		{
			len++;
			buff[ibuf] = '\0';
			ibuf = 0;
			double f = atof(buff);
			out[idata++] = f;

			if (ch == EOF)
			{
				if (!buff[0])
					len--;
				break;
			}
		}
	}
	fclose(fp);
	return len;
}

Result match(double* in1, int in1len, Data& data)
{
	Result res;

	int max_scalar = (int)(data.len / 2.0 / in1len);

	if (max_scalar > 10)
		max_scalar = 10;

	if (max_scalar <= 1.5)
		return res;

	int* extreme1 = new int[in1len];
	memset(extreme1, 0, sizeof(int)*in1len);
	zigzag(in1, in1len, extreme1, 2);
	double* normalized1 = new double[in1len];
	normalize(in1, in1len, extreme1, normalized1);
	double mu = mean(normalized1, in1len);
	double sigma = stddev(normalized1, in1len);
	for (int i = 0; i < in1len; i++)
	{
		normalized1[i] = (normalized1[i] - mu) / sigma;
	}

	std::string cache_path = "kline\\cache\\" + std::string(data.name) + ".cache";
	double* normalized2 = new double[data.len + 10];
	int ret = read_data(cache_path.c_str(), normalized2);
	
	if (ret == -1)
	{
		int* extreme2 = new int[data.len];
		memset(extreme2, 0, sizeof(int)*data.len);
		zigzag(data.data, data.len, extreme2, 5);
		normalize(data.data, data.len, extreme2, normalized2);
		FILE* f = fopen(cache_path.c_str(), "w");
		for (int i = 0; i < data.len; i++)
		{
			fprintf(f, "%lf\n", normalized2[i]);
		}
		fclose(f);
		delete extreme2;
	}

	int startpos = data.len / 2 - in1len / 2;
	
	

	double scalar = (max_scalar + 1) / 2.0;

	double T0 = 1000;
	double T = T0;
	double Tmin = 0.00001;
	double last_sim = 0xFFFFFFFF;

	while (T > Tmin)
	{	
		double _similarity = 0xFFFFFFFF;
		int _startpos = 0;
		double _scalar = 0;

		for (int i = 0; i < 3; i++)
		{
			int __startpos = 0;
			double __scalar = 0;

			int rnd = rand() % 2;
			if (rnd == 1)
			{
				__scalar = (double)(((int)((scalar + 0.1) * 10 - 10)) % (10 * (max_scalar - 1))) / 10 + 1;
			}
			else
			{
				__scalar = (double)(((int)((scalar - 0.1) * 10 - 10)) % (10 * (max_scalar - 1))) / 10 + 1;
			}

			rnd = rand() % 2;
			if (rnd == 1)
			{
				__startpos = (startpos + data.len + 1) % (data.len - (int)(in1len*__scalar));
			}
			else
			{
				__startpos = (startpos + data.len - 1) % (data.len - (int)(in1len*__scalar));
			}

			double* scaled = new double[(int)(__scalar*in1len)];
			scale(normalized1, in1len, __scalar, scaled);
			double __similarity = similarity(scaled, normalized2 + __startpos, __scalar*in1len);

			if (__similarity < _similarity)
			{
				_similarity = __similarity;
				_startpos = __startpos;
				_scalar = __scalar;
			}

			delete scaled;
		}

		if (_similarity < last_sim)
		{
			last_sim = _similarity;
			startpos = _startpos;
			scalar = _scalar;
		}

		else
		{
			double p = exp((last_sim - _similarity) / T);
			int rnd = (double)(rand() % 100000) / 100000;
			if (rnd < p)
			{
				last_sim = _similarity;
				startpos = _startpos;
				scalar = _scalar;
			}
		}

		T = 0.99*T;
	}

	res.scalar = scalar;
	res.startpos = startpos;
	res.similarity = last_sim;

	delete extreme1;
	delete normalized1;
	delete normalized2;

	return res;
}

std::vector<Data> read_all_data(const std::string& directory)
{
	std::vector<Data> data;
	_finddata_t file_info;
	std::string current_path = directory + "\\*.*";
	int handle = _findfirst(current_path.c_str(), &file_info);
	if (-1 == handle)
		return data;
	do
	{
		if (file_info.attrib != _A_SUBDIR)
		{
			double* ptr = new double[5000];
			std::string path = directory + "\\" + file_info.name;
			int len = read_data(path.c_str(), ptr);
			Data d;
			d.data = ptr;
			d.len = len;
			strcpy(d.name, file_info.name);
			data.emplace_back(d);
		}
	} while (!_findnext(handle, &file_info));
	_findclose(handle);
	return data;
}

int main(int argc, char* argv[])
{
	if (argc == 2 && strcmp(argv[1], "-zigzag")==0)
	{
		double input[5000];
		int len = read_data("kline\\input.txt", input);

		int* zz = new int[len];
		memset(zz, 0, sizeof(int)*len);
		int maxrecursion = (int)(pow((double)len / 15, 0.333));
		if (maxrecursion > 5)
			maxrecursion = 5;
		zigzag(input, len, zz, maxrecursion);
		FILE* f = fopen("kline\\zigzag.txt", "w");
		for (int i = 0; i < len; i++)
		{
			if (zz[i] != 0)
			{
				fprintf(f, "%d\n", 1);
			}
			else
			{
				fprintf(f, "%d\n", 0);
			}
		}
		fclose(f);
		return 0;
	}

	srand((unsigned int)time(NULL));
	auto data = read_all_data("kline\\data");
	double input[5000];
	int len = read_data("kline\\input.txt", input);
	FILE* fout = fopen("kline\\out.txt", "w");
	for (int i = 0; i < data.size(); i++)
	{
		Result res = match(input, len, data[i]);
		if (res.startpos == -1)
			continue;
		fprintf(fout, "%s, %d, %d, %lf\n", data[i].name, res.startpos, (int)(res.startpos + res.scalar*len), res.similarity);
	}

	fclose(fout);
	return 0;
}